package com.wrial.kind.doublepointer;
/*
 * @Author  Wrial
 * @Date Created in 11:04 2020/8/19
 * @Description 和为s的连续正数序列
 *
    输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
    序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
    示例 1：
    输入：target = 9
    输出：[[2,3,4],[4,5]]
    示例 2：
    输入：target = 15
    输出：[[1,2,3,4,5],[4,5,6],[7,8]]

 */

import java.util.ArrayList;
import java.util.List;

public class FindContinuousSequence {

    /**
     * 使用滑动窗口来实现，数值小了 right++ 数值大了 left++  相等就加入结果并一定left++
     * （一定不要忘了每一步对curSum的更新）
     */
    public int[][] findContinuousSequence(int target) {

        List<int[]> ans = new ArrayList<>();
        int left = 1, right = 1, curSum = 0;
        while (left <= target / 2) {
            if (curSum > target) {
                curSum -= left;
                left++;
            } else if (curSum < target) {
                curSum += right;
                right++;
            } else {
                int[] temp = new int[right - left];
                for (int i = left; i < right; i++) {
                    temp[i - left] = i;
                }
                curSum -= left; //这一步一定不能忘记
                left++;
                ans.add(temp);
            }
        }
        int[][] ret = new int[ans.size()][];
        for (int i = 0; i < ans.size(); i++) {
            ret[i] = ans.get(i);
        }

        return ret;
    }
}
